/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
 var sortList = function(head) {
    return recursion(head);
    function recursion(head){  // 递归
        if(head==null || head.next==null){
            return head;
        }
        let fast=head,slow=head,middle;
        while(fast!=null && fast.next!=null){   // 查找中点
            middle=slow;
            fast=fast.next.next;
            slow=slow.next;
        }
        middle.next=null;       // 分割链表，防止生成环
        // console.log(head,slow);
        return merge(recursion(head),recursion(slow));  // 递归合并

    }
    function merge(head1,head2){  //有序合并
        let newhead=new ListNode();
        let node = newhead;
        while(head1!=null && head2!=null){
            if(head1.val<head2.val){
                node.next=head1;
                node=node.next;
                head1=head1.next;
            }
            else{
                node.next=head2;
                node=node.next;
                head2=head2.next;
            }
        }
        node.next= head1 || head2;
        // console.log(newhead.next);
        return newhead.next;
    }
};

function ListNode(val, next) {
    this.val = (val===undefined ? 0 : val)
    this.next = (next===undefined ? null : next)
 }
function list(arr){
let length=arr.length;
let head=new ListNode();
let node = head;
for(let i=0;i<length;i++){
    node.next=new ListNode(arr[i]);
    node=node.next;
}
return head.next;
}

let arr=[4,2,1,3];
let head=list(arr);
console.log(sortList(head));

